package com.lw.leetcode.binary.a;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 2248. 多个数组求交集
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/26 10:49
 */
public class Intersection {

    public static void main(String[] args) {
        Intersection test = new Intersection();

        // []
        int[][] arr = {{1, 2, 3}, {4, 5, 6}};

        // [3,4]
//        int[][] arr = {{3, 1, 2, 4, 5}, {1, 2, 3, 4}, {4, 5, 6}};

        List<Integer> intersection = test.intersection(arr);
        System.out.println(intersection);
    }

    public List<Integer> intersection(int[][] nums) {
        int length = nums.length;
        int[] arr = new int[length];
        int[] num = nums[0];
        int n = num.length;
        List<Integer> list = new ArrayList<>(n);
        for (int[] ints : nums) {
            Arrays.sort(ints);
        }
        for (int i = 0; i < n; i++) {
            int k = num[i];
            boolean f = true;
            for (int j = 1; j < length; j++) {
                int[] ints = nums[j];
                int b = ints.length;
                int st = arr[j];
                while (st < b && ints[st] < k) {
                    st++;
                }
                if (st < b && ints[st] == k) {
                    arr[j] = st + 1;
                } else {
                    arr[j] = st;
                    f = false;
                    break;
                }
            }
            if (f) {
                list.add(k);
            }
        }
        return list;
    }

}
